package com.example.algorithm.recursion;

public class Leetcode50_MyPow {
    public static void main(String[] args) {

        // 32768.0
        // 2.00000
        //-2147483648
        double v = new Solution().myPow(2.00000, -2147483648);
        System.out.println(v);

    }

    static class Solution {
        public double myPow(double x, int n) {
//            return n > 0 ? pow(x, n) : 1 / pow(x, -n);
//            return n >= 0 ? quickPowByIteration(x, n) : 1 / quickPowByIteration(x, -n);
            return n > 0 ? quickPow(x, n) : 1 / quickPow(x, -n);
        }

        /**
         * 直接依次计算(StackOverflowError)
         * @param x
         * @param n
         * @return
         */
        private double pow(double x, int n) {
            if (n == 0) return 1.0;
            double tmp = pow(x, n - 1);
            return tmp * x;
        }

        /**
         * 快速pow递归实现
         * @param x
         * @param n
         * @return
         */
        private double quickPow(double x, int n) {
            if (n == 0) return 1.0;
            double tmp = quickPow(x , n / 2);
            return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
        }

        private double quickPowByIteration(double x, int n) {
            if (n == 0) return 1.0;
            double res = 1.0;
            double tmp = x;
            while ( n  > 0) {
                if (n % 2 == 1) {
                    res = res * tmp;
                }
                tmp *= tmp;
                n /=  2;
            }
            return res;
        }
    }
}
